class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    public int maxProfit(int[] p) {
        /**
         * 买卖股票的最佳时期Ⅲ
         * 状态表示：
         * 	f[i][j] 表示第j天为结尾，处于第i次交易，并且状态为可交易，此时的最大利润
         * 	g[i][j] 表示第j天为结尾，处于第i次交易，并且状态为持有，此时最大利润
         * 状态转移方程：
         *  // 持有 =》 可交易，此时已经完成了一次交易，因此交易次数需要-1
         *  // - 前一天为可交易 或者 前一天为持有且当前卖掉股票转为可交易
         * 	f[i][j] = Math.max(f[i][j-1], g[i-1][j-1] + p[i]);
         *
         *	// - 前一天为持有 或者 前一天为可交易且当天买入股票转为持有
         * 	g[i][j] = Math.max(g[i][j-1], f[i][j-1] - p[i]);
         * 初始化：
         * 	g第一行第一列初始化为 -p[0]
         * 填表顺序：
         * 	从1，1下标开始，从上到下，从左到右
         * 返回值：
         * 	return 可交易状态最后一天不同交易次数的最大值
         * */
        // 1 预处理
        int n = p.length;
        int count = 2;
        // 2 创建dp表
        int[][] f = new int[count+1][n];
        int[][] g = new int[count+1][n];
        // 3 初始化
        for(int k = 0; k <= count; k++) {
            g[k][0] = -p[0];
        }
        for(int k = 1; k < n; k++) {
            g[0][k] = Math.max(g[0][k-1], -p[k]);
        }
        // 4 填表
        for(int i = 1; i <= count; i ++) {
            for(int j = 1; j < n; j++) {
                f[i][j] = Math.max(f[i][j-1], g[i-1][j-1] + p[j]);
                g[i][j] = Math.max(g[i][j-1], f[i][j-1] - p[j]);
            }
        }
        // 5 返回值
        // for(int k = 0; k <= count; k++) {
        // 	for(int h = 0; h < n; h++) {
        // 		System.out.print(f[k][h] + " ");
        // 	}
        // 	System.out.println();
        // }
        int ret = 0;
        for(int k = 0; k <= count; k++) {
            if(f[k][n-1] > ret) ret = f[k][n-1];
        }
        return ret;
    }
}